class ListNode {
       int val;
       ListNode next;
       ListNode(int x) {
          val = x;
           next = null;
       }
}

public class Solution {
    /**
     * 给你一个链表的头节点 head,判断链表中是否有环?
     * @param head 链表头节点
     * @return 链表有环返回true,否则返回false
     */
    public boolean hasCycle(ListNode head) {
        //链表为空,一定无环
        if (head == null) return false;
        //链表仅有一个元素且next为null,一定无环
        if (head.next == null) return false;
        //慢指针
        ListNode slow = head;
        //快指针
        ListNode fast = head.next;
        //快慢指针不相遇,快慢指针一直移动
        while(slow != fast) {
            //快指针next域为null则一定无环或快指针的下一个节点next域为空也一定无环
            if (fast.next == null || fast.next.next == null) return false;
            slow = slow.next;//慢指针走一步
            fast = fast.next.next;//快指针走两步
        }
        //快慢指针相遇,循环结束
        return true;
    }
}